package org.czl.tree;

public class l2684 {
    public static void main(String[] args) {
        //[187,167,209,251,152,236,263,128,135],[267,249,251,285,73,204,70,207,74],[189,159,235,66,84,89,153,111,189]
        System.out.println(maxMoves(new int[][]{{187,167,209,251,152,236,263,128,135},{267,249,251,285,73,204,70,207,74},
                {189,159,235,66,84,89,153,111,189}}));
    }
    public static int maxMoves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 2][n];
        int ans = 0;
        for(int j = 1; j < n; j++){
            int i = 0;
            for(; i < m; i++){
                if(i - 1 >= 0 && j - 1 >= 0&& grid[i][j] > grid[i - 1][j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if(j - 1 >=0 && grid[i][j] > grid[i][j - 1]){
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + 1);
                }
                if(i + 1 < m && j - 1 >=0 && grid[i][j] > grid[i + 1][j - 1]){
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 1);
                }
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
}
